package 链表;

/**
 * https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class _206_反转链表 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(3, null)));
        ListNode result = reverseList2(listNode1);
        System.out.println(result);
    }

    //递归
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList1(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    //迭代 1->2->3->4->5->null
    public static ListNode reverseList2(ListNode head) {
        ListNode newNode = null;
        while (head != null) {
            //1.临时变量保存当前head.next,为了提供给下一次循环 ListNode tmp = 2
            ListNode tmp = head.next;
            //2.当前变量指向newNode == 2->null
            head.next = newNode;
            //3.把newNode指向head,提供给下一次第二部指向 newNode = 1
            newNode = head;
            //4.再把当前head变为tmp，也就是head从1，变成了2
            head = tmp;
        }

        return newNode;
    }
}
